#include "crosslist.h"
#include <stdio.h>
#include <stdlib.h>

int init_cross_list(PCrossList L, const ElemType* A, int m, int n)
{
    int num = 0, i, j, k;
    OLNode* p;
    OLNode* q;

    L->rows = m;
    L->cols = n;

    if (!(L->rowhead = (OLink*)malloc(m * sizeof(OLink))))
        return 0;
    if (!(L->colhead = (OLink*)malloc(n * sizeof(OLink))))
        return 0;
    for (k = 0; k < m; k++)
        L->rowhead[k] = NULL;
    for (k = 0; k < n; k++)
        L->colhead[k] = NULL;
    for (k = 0; k < m * n; k++) {
        if (A[k] == 0) {
            continue;
        } else {
            p = (OLink)malloc(sizeof(OLNode));
            p->row = k / n; //从0行0列开始
            p->col = k % n;
            p->value = A[k];
            p->right = NULL;
            p->down = NULL;

            i = p->row;
            if (L->rowhead[i] == NULL) {
                L->rowhead[i] = p;
            } else {
                for (q = L->rowhead[i]; q->right && q->right->col < p->col; q = q->right)
                    ;
                p->right = q->right;
                q->right = p;
            }

            j = p->col;
            if (L->colhead[j] == NULL) {
                L->colhead[j] = p;
            } else {
                for (q = L->colhead[j]; q->down && q->down->row < p->row; q = q->down)
                    ;
                p->down = q->down;
                q->down = p;
            }
            num++;
        }
    }
    L->nums = num;
    return num;
}

int del_cross_list(PCrossList L, ElemType k)
{
    int i = 0, j = 0, t = 0;

    OLink p = NULL; //我们要操作的节点
    OLink templeft = NULL; //操作节点左边的节点
    OLink tempup = NULL; //操作节点上边的节点

    for (; i < L->rows; i++) { //按行检索
        if (L->rowhead[i] == NULL) { //如果这一行为空，则直接跳到下一行
            continue;
        }

        for (p = L->rowhead[i]; p != NULL; p = p->right) { //每行里面从左到右依次检索
            if (p->value == k) { //若当前节点就是要删除的节点
                for (templeft = L->rowhead[i]; templeft->right != NULL && templeft->right->col < p->col; templeft = templeft->right)
                    ;
                for (tempup = L->colhead[p->col]; tempup->down != NULL && tempup->down->row < p->row; tempup = tempup->down)
                    ;

                //找到他左边和上边的节点并记录
                if (templeft == p) { //左边没有节点
                    if (tempup == p) { //并且上边也没有节点
                        L->rowhead[i] = p->right;
                        L->colhead[p->col] = p->down;
                        free(p);
                    } else { //上边有节点
                        L->rowhead[i] = p->right;
                        tempup->down = p->down;
                        free(p);
                    }
                } else { //左边有节点
                    if (tempup == p) { //上边没有节点
                        templeft->right = p->right;
                        L->colhead[p->col] = p->down;
                        free(p);
                    } else { //上边有节点
                        templeft->right = p->right;
                        tempup->down = p->down;
                        free(p);
                    }
                }
                t++;
                L->nums--;
            }
        }
    }
    return t;
}
